UVa/10902 - Pick-up sticks/10902.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <list>
  19 #include <map>
  20 #include <set>
  21
  22 #define D(x) cout << #x " is " << x << endl
  23
  24
  25 /*
  26   Returns true if point (x, y) lies inside (or in the border)
  27   of box defined by points (x0, y0) and (x1, y1).
  28 */
  29 bool point_in_box(double x, double y,
  30                   double x0, double y0,    double x1, double y1){
  31   return min(x0, x1) <= x && x <= max(x0, x1) && min(y0, y1) <= y && y <= max(y0, y1);
  32 }
  33
  34 /*
  35   Finds the intersection between two segments (Not infinite lines!)
  36   Segment 1 goes from point (x0, y0) to (x1, y1).
  37   Segment 2 goes from point (x2, y2) to (x3, y3).
  38
  39   Handles the case when the 2 segments are:
  40   *Parallel but don't lie on the same line (No intersection)
  41   *Parallel and both lie on the same line (Infinite intersections or no intersections)
  42   *Not parallel (One intersection or no intersections)
  43
  44   Returns true if the segments do intersect in any case.
  45 */
  46 bool segment_segment_intersection(double x0, double y0,   double x1, double y1,
  47                                   double x2, double y2,   double x3, double y3){
  48 #ifndef EPS
  49 #define EPS 1e-9
  50 #endif
  51
  52   double t0 = (y3-y2)*(x0-x2)-(x3-x2)*(y0-y2);
  53   double t1 = (x1-x0)*(y2-y0)-(y1-y0)*(x2-x0);
  54   double det = (y1-y0)*(x3-x2)-(y3-y2)*(x1-x0);
  55   if (fabs(det) < EPS){
  56     //parallel
  57     if (fabs(t0) < EPS || fabs(t1) < EPS){
  58       //they lie on same line, but they may or may not intersect.
  59       return (point_in_box(x0, y0,   x2, y2, x3, y3) ||
  60               point_in_box(x1, y1,   x2, y2, x3, y3) ||
  61               point_in_box(x2, y2,   x0, y0, x1, y1) ||
  62               point_in_box(x3, y3,   x0, y0, x1, y1));
  63     }else{
  64       //just parallel, no intersection
  65       return false;
  66     }
  67   }else{
  68     t0 /= det;
  69     t1 /= det;
  70     /*
  71       0 <= t0 <= 1 if the intersection point lies in segment 1.
  72       0 <= t1 <= 1 if the intersection point lies in segment 2.
  73     */
  74     if (0.0 <= t0 && t0 <= 1.0 && 0.0 <= t1 && t1 <= 1.0){
  75       double x = x0 + t0*(x1-x0);
  76       double y = y0 + t0*(y1-y0);
  77       //intersection is point (x, y)
  78       return true;
  79     }
  80     //the intersection points doesn't lie on both segments.
  81     return false;
  82   }
  83 }
  84
  85 typedef pair<double, double> point;
  86 typedef pair<point, point> segment;
  87 int main(){
  88   int n;
  89   while (scanf("%d", &n) && n){
  90     vector<segment> sticks;
  91     list<int> top;
  92     for (int i=0; i<n; ++i){
  93       double x0, y0, x1, y1;
  94       scanf("%lf %lf %lf %lf", &x0, &y0, &x1, &y1);
  95       sticks.push_back(segment(point(x0, y0), point(x1, y1)));
  96       for (list<int>::iterator j = top.begin(); j != top.end(); ++j){
  97         const segment &s = sticks[*j];
  98         bool b = segment_segment_intersection(s.first.first, s.first.second,
  99                                               s.second.first, s.second.second,
 100                                               x0, y0, x1, y1);
 101         /*
 102         printf("Intersection between <(%.2lf, %.2lf) - (%.2lf, %.2lf)> and "
 103                "<(%.2lf, %.2lf) - (%.2lf, %.2lf)> = %s\n", x0, y0, x1, y1,
 104                s.first.first, s.first.second, s.second.first, s.second.second,
 105                (b ? "true" : "false"));
 106         */
 107
 108         if (b) j = top.erase(j), --j;
 109       }
 110       top.push_back(i);
 111     }
 112     printf("Top sticks:");
 113     int k = 0;
 114     for (list<int>::iterator i = top.begin(); k < top.size(); ++i, ++k){
 115       printf(" %d%c", *i + 1, (k < top.size()-1 ? ',' : '.'));
 116     }
 117     printf("\n");
 118   }
 119   return 0;
 120 }